package org.lql.algo.codecrush.week007;

/**
 * @author: liangqinglong
 * @date: 2025-08-18 13:52
 * @description: 74. 搜索二维矩阵 <a href="https://leetcode.cn/problems/search-a-2d-matrix/description/">...</a>
 **/
public class SearchMatrix {

	public boolean searchMatrix(int[][] matrix, int target) {
		int m = matrix.length;
		int n = matrix[0].length;
		int left = 0;
		int right = m * n - 1;
		while (left <= right) {
			int mid = left + (right - left) / 2;
			int midVal = matrix[mid / n][mid % n]; // 获取中间元素的值 mid / n 表示行数，mid % n 表示列数
			if (midVal == target) {
				return true;
			} else if (midVal > target) {
				right = mid - 1;
			} else {
				left = mid + 1;
			}
		}
		return false;
	}

	public static void main(String[] args) {
		SearchMatrix sm = new SearchMatrix();
		int[][] matrix = new int[][]{{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 50}};
		int target = 3;
		System.out.println(sm.searchMatrix(matrix, target));
		target = 13;
		System.out.println(sm.searchMatrix(matrix, target));
	}
}
